﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace ImryStefanVRPprogram
{

    class Program
    {
        public static Random rand;

        // Slower if true!!! Set to true if don't trust my efficient distance and capacity updates
        public static bool DEBUG = false;

        // Global variable, for convenience
        public static CVRPData vrpData;

        static void Main(string[] args)
        {
            Console.WriteLine("Welcome to our Simulated Annealing implementation");

            Stopwatch stopWatch = new Stopwatch();

            stopWatch.Start();

            rand = new Random();

            // If there are command line arguments, the first one is the file name
            String inputFileName;
            if (args.Length != 0)
                inputFileName = args[0];
            else
                inputFileName = "Example1.vrp";

            // Create the parser object, and read in all the data from file. This object can read ANY TSPLIB file. Code borrowed from HeuristicLab.
            TSPLIBParser myParser = new TSPLIBParser(inputFileName);
            myParser.Parse();

            // Create the global vrp data object, using the parsed data
            Program.vrpData = new CVRPData(myParser);

            // Get initial solution
            CVRPSolution currentSolution = SavingsMethodHeuristic();
            double totalCostInitial = currentSolution.totalCost;
            int numRoutesInitial = currentSolution.listOfRoutes.Count();

            // Run the metaheuristic
            CVRPSolution mySolution = SimulatedAnnealing(currentSolution, 5, stopWatch);
            double totalCostFinal = mySolution.totalCost;
            int numRoutesFinal = mySolution.listOfRoutes.Count();

            // Check if solution makes sense
            mySolution.FeasibilityCheck();

            // Calculate the total time
            stopWatch.Stop();
            TimeSpan ts = stopWatch.Elapsed;

            // Output the solution to file
            //mySolution.WriteToFile(inputFileName + ".opt", ts);

            // Output the statistics to csv
            string teamName = "ImryStefan";
            string outputFile = teamName + ".csv";
            using (StreamWriter writer = new StreamWriter(outputFile, true))
            {
                writer.WriteLine(teamName + ", " + inputFileName + ", " + totalCostInitial + ", " + numRoutesInitial + ", " + totalCostFinal + ", " + numRoutesFinal);
                writer.Close();
            }

            // Uncomment to run from Visual Studio
            //Console.WriteLine("Press any key to exit.");
            //Console.ReadKey();

        }

        private static CVRPSolution SimulatedAnnealing(CVRPSolution currentSolution, double maxMinutes, Stopwatch stopWatch)
        {
            CVRPSolution currentBestSolution = currentSolution.Clone();
            TimeSpan timeOfLastImprovement = stopWatch.Elapsed;
            double temperature = 1;
            while (true)
            {
                if (stopWatch.Elapsed.TotalMinutes > maxMinutes)
                    break;
                ChangeInSolution theChangeInSolution = NeighboorhoodSearches.GetGoodSolutionInANeighborhood(currentSolution);

                if (currentSolution.totalCost < currentBestSolution.totalCost - 1e-6) // Trial cost is better that current best cost. Accept and decrease temperature.
                {
                    Console.WriteLine("Accepted as new best = " + currentSolution.totalCost);
                    currentBestSolution = currentSolution.Clone();
                    temperature = temperature * 0.9;
                    timeOfLastImprovement = stopWatch.Elapsed;
                }
                else if (currentSolution.totalCost > theChangeInSolution.totalCostBeforeChange && rand.NextDouble() > temperature) // Trial cost is bad, and we are out of luck. Don't accept the move (undo it)
                    currentSolution.UndoChange(theChangeInSolution);

                // Hopfully helpful in getting out of local minima
                if (stopWatch.Elapsed.TotalSeconds - timeOfLastImprovement.TotalSeconds > 60)
                {
                    temperature = 1;
                    timeOfLastImprovement = stopWatch.Elapsed;
                    Console.WriteLine("Making a Huge Jump!!!");
                    NeighboorhoodSearches.HugeJump(currentSolution);
                }

            }
            return currentBestSolution;
        }

        private static CVRPSolution SavingsMethodHeuristic()
        {
            Console.WriteLine("Starting the SavingsMethodHeuristic");

            //The savings list
            List<SavingsCouple> Savings = new List<SavingsCouple>();
            //Go over all possible couples once and create a coupling, we rely on the fact that the distances are symmetric
            for (int i = 1; i < Program.vrpData.Dimension; i++)
            {
                for (int j = 1; j < Program.vrpData.Dimension; j++)
                {
                    if (j != i)
                    {
                        SavingsCouple cpl = new SavingsCouple();
                        cpl.FirstNode = i;
                        cpl.SecondNode = j;
                        cpl.Saving = Program.vrpData.Distances[i, 0] + Program.vrpData.Distances[0, j] - Program.vrpData.Distances[i, j];
                        Savings.Add(cpl);
                    }
                }

            }

            Savings = Savings.OrderByDescending(x => x.Saving).ToList();

            // Current tour list. Populated in the following loop, and will have tours removed and added as the heuristic progresses.
            List<VehicleRoute> Tours = new List<VehicleRoute>();
            // List of nodes that are either at the start of a tour or at the end. These can be merged. Initially all nodes are in the list.
            List<int> availNodes = new List<int>();
            // Create the inital tours
            Console.WriteLine("Start creating the initial routes");
            for (int i = 1; i < Program.vrpData.Dimension; i++)
            {
                VehicleRoute tour = new VehicleRoute(i);
                tour.totalDemandOnRoute = vrpData.Demands[i];
                tour.totalDistanceOfRoute = 2 * vrpData.Distances[0, i];
                Tours.Add(tour);
                availNodes.Add(i);
            }
            Console.WriteLine("Finished creating the initial routes");

            //We will iterate through the savings list
            for (int i = 0; i < Savings.Count; i++)
            {
                //flag variable that indicate if both nodes in savings couple are at the extremites of a tour
                int flag = 0;

                //check if the nodes are in the extremites
                for (int j = 0; j < availNodes.Count; j++)
                    if ((availNodes[j] == Savings[i].FirstNode) || (availNodes[j] == Savings[i].SecondNode))
                        flag++;

                //If the nodes are at the extremities, try to merge
                if (flag == 2)
                {
                    //Console.WriteLine("Trying to merge since nodes are extremeties");
                    //we need to find the two tours that contain the nodes
                    //id of the tours
                    int indexOfFirstRoute = -1;
                    int indexOfSecondRoute = -1;

                    for (int j = 0; j < Tours.Count; j++)
                    {
                        //We found the tour that finishes with the first node
                        if (Tours[j].GetNodeAt(Tours[j].GetNumberOfNodesVisited()) == Savings[i].FirstNode)
                            indexOfFirstRoute = j;
                        //We found the tour that starts with the second node
                        if (Tours[j].GetNodeAt(1) == Savings[i].SecondNode)
                            indexOfSecondRoute = j;
                    }

                    // Merge routes if:
                    // 1. pair from savings finishes one route and starts another
                    // 2. its not the same route
                    // 3. capacity not violated by merging
                    if (indexOfSecondRoute >= 0 && indexOfFirstRoute >= 0 && indexOfSecondRoute != indexOfFirstRoute && Tours[indexOfFirstRoute].totalDemandOnRoute + Tours[indexOfSecondRoute].totalDemandOnRoute <= Program.vrpData.Capacity)
                    {
                        int newlength = Tours[indexOfFirstRoute].GetNumberOfNodesVisited() + Tours[indexOfSecondRoute].GetNumberOfNodesVisited();

                        // Create a new sequence of nodes which corresponds to the merged route. It will include nodes from both routes
                        List<int> tour = new List<int>();
                        double distCalculated = 0;
                        tour.Add(0);
                        int j = 0;
                        for (j = 0; j < newlength; j++)
                        {
                            if (j < Tours[indexOfFirstRoute].GetNumberOfNodesVisited())
                                tour.Add(Tours[indexOfFirstRoute].GetNodeAt(j + 1));
                            else
                            {
                                //subtract the length of tour A
                                int normIndex = j - Tours[indexOfFirstRoute].GetNumberOfNodesVisited();
                                tour.Add(Tours[indexOfSecondRoute].GetNodeAt(normIndex + 1));
                            }
                            distCalculated += vrpData.Distances[tour[j], tour[j + 1]];
                        }
                        distCalculated += vrpData.Distances[tour[j], 0];
                        tour.Add(0);
                        VehicleRoute Tour = new VehicleRoute(tour);
                        Tour.totalDistanceOfRoute = distCalculated;
                        Tour.totalDemandOnRoute = Tours[indexOfFirstRoute].totalDemandOnRoute + Tours[indexOfSecondRoute].totalDemandOnRoute;
                        //add the combined tour and remove the old ones
                        Tours.Add(Tour);

                        // If the any of the tours merged are of length greater than 2, their corresponding extreme (starting or ending) node cannot
                        // be merged anymore. It can be removed from the savings list.
                        if (Tours[indexOfFirstRoute].GetNumberOfNodesVisited() > 1)
                            availNodes.Remove(Tours[indexOfFirstRoute].GetLastNodeVisited());
                        if (Tours[indexOfSecondRoute].GetNumberOfNodesVisited() > 1)
                            availNodes.Remove(Tours[indexOfSecondRoute].GetNodeAt(1));

                        // Remove the merged routes from the route list.
                        Tours.RemoveAt(indexOfFirstRoute);
                        if (indexOfFirstRoute > indexOfSecondRoute)
                            Tours.RemoveAt(indexOfSecondRoute);
                        else
                            Tours.RemoveAt(indexOfSecondRoute - 1);
                    }
                }
            }

            //Tours now contain the solution
            CVRPSolution sol = new CVRPSolution();
            sol.listOfRoutes = new List<VehicleRoute>();

            double heuristicTotalCost = 0;
            for (int i = 0; i < Tours.Count; i++)
            {
                sol.listOfRoutes.Add(Tours[i]);
                heuristicTotalCost += Program.vrpData.Distances[0, sol.listOfRoutes[i].GetNodeAt(1)] + Program.vrpData.Distances[sol.listOfRoutes[i].GetLastNodeVisited(), 0];
                for (int j = 0; j < sol.listOfRoutes[i].GetNumberOfNodesVisited() - 1; j++)
                    heuristicTotalCost += Program.vrpData.Distances[sol.listOfRoutes[i].GetNodeAt(j + 1), sol.listOfRoutes[i].GetNodeAt(j + 2)];
            }
            sol.totalCost = heuristicTotalCost;
            Console.WriteLine("Heuristic done.\nTotalcost : " + sol.totalCost);
            return sol;
        }
    }
}
